package javaCode;


import java.util.ArrayList;
import java.util.List;

/**
 * Created by lxy_920912 on 2017/1/11.
 */
public class LeetCode235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        List<TreeNode> path = new ArrayList<>();
        List<List<TreeNode>> list =new ArrayList<>();

        findPath(root,p,path,list);
        path.clear();
        findPath(root,q,path,list);
        List<TreeNode> pPath = list.get(0);
        List<TreeNode> qPath = list.get(1);
        int i = 0;
        for( i = 0;i < pPath.size()&&i<qPath.size();i++){
            if(pPath.get(i) != qPath.get(i)){
                break;
            }
        }
        TreeNode result = pPath.get(i-1);
        return  result;


    }
    public void findPath(TreeNode root,TreeNode p,List<TreeNode> path,List<List<TreeNode>> list ){
        if(root != null){
            path.add(root);
            if(root.val == p.val){
                List<TreeNode> newPath = new ArrayList<>();
                newPath.addAll(path);
                list.add(newPath);
            }else{
                findPath(root.left,p,path,list);
                findPath(root.right,p,path,list);
                path.remove(root);


            }
        }

    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val >q.val){
            return lowestCommonAncestor2(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor2(root.right,p,q);
        }
        return root;

    }


}
